/*
 * @lc app=leetcode.cn id=56 lang=cpp
 *
 * [56] 合并区间
 */

#include <limits.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;             // 保存合并后的区间
        int length = intervals.size();          // 记录初始区间的个数
        
        // 特判初始区间为空的情况
        if (length == 0) return result;

        // 区间排序，按照第一个元素升序的顺序
        sort(intervals.begin(), intervals.end());

        vector<int> interval;
        interval.push_back(intervals[0][0]);
        interval.push_back(intervals[0][1]);
        for (int i = 0; i < length; i++) {
            
            if (intervals[i][0] <= interval[1]) {
                // 如果可以合并，则修改当前区间的右端点
                interval[1] = max(interval[1], intervals[i][1]);
            } else {
                // 如果不能合并，保存当前区间                
                result.push_back(interval);
                interval[0] = intervals[i][0];
                interval[1] = intervals[i][1];
            }
        }
        result.push_back(interval);
        
        return result;
    }
};
// @lc code=end

